I spent the weekend using almost exclusively my Chromebook 13, on a single charge Saturday and Sunday. Keyboard I think I like the keyboard better now than I used to when I first tried it. It gets nowhere near the ThinkPad X230 one, though; appart from the coating, which my (backlit) X230 unfortunately does not have. Screen While the screen appeared very grainy to me on first sight, having only used IPS screens in the past year, I got used to it over the weekend. I now do not notice much graininess anymore. The contrast still seems extremely poor, the colors are not vivid, and the vertical viewing angles are still a disaster, though. Battery life I think the battery life is awesome. I have 30% remaining now while I am writing this blog post and Chrome OS tells me I still have 3 hours and 19 minutes remaining. It could probably still be improved though, I notice that Chrome OS uses 7-14% CPU in idle normally (and up to 20% in exceptional cases). The maximum power usage I measured using the battery s internal sensor was about 9.2W, that was with 5 Big Buck Bunny 1080p videos played in parallel. Average power consumption is around 3-5W (up to 6.5 with single video playing), depending on brightness, and use. Performance While I do notice a performance difference to my much more high-end Ivy Bridge Core i5 laptop, it turns out to be usable enough to not make me want to throw it at a wall. Things take a bit longer than I am used to, but it is still acceptable. Input: Software Part The user interface is great. There are a lot of gestures available for navigating between windows, tabs, and in the history. For example, horizontally swiping with two finger moves in history, three fingers moves between tabs; and swiping down (or up for Australian scrolling) gives an overview of all windows (like expose on Mac, GNOME s activities, or the multi-tasking thing Maemo used to have). What I miss is a keyboard shortcut like Meta + Left/Right on GNOME which moves the active window to the left/right side of the screen. That would be very useful for mult-tasking situations. Issues I noticed some performance issues. For example, I can easily get the Chromebook to use 85% of a CPU by scrolling on a page with the touchpad or 70% for scrolling by keeping a key pressed (crbug.com/420452). While watching Big Buck Bunny on YouTube, I noticed some (micro) stuttering in the beginning of the film, as well as each time I move in or out of the video area when not in full-screen mode (crbug.com/420582). It also increases CPU usage to about 70%. Running a proper Linux? Today, I tried to play around a bit with Debian wheezy and Ubuntu trusty systems, in a chroot for now. I was trying to find out if I can get an accelerated X server with the standard ChromeOS kernel. The short answer is: No. I tried two things:

1. Debian wheezy with the binaries from ChromeOS (they have the same xserver version)
2. Ubuntu trusty with the Nvidia drivers

Unfortunately, they did not work. Option 1 failed because ChromeOS uses glibc 2.15 whereas wheezy uses 1.13. Option 2 failed because the sysfs interface is different between the ChromeOS and Linux4Tegra kernels. I guess I ll have to wait. I also tried booting a custom kernel from USB, but given that the u-boot always sets console= and there is no non-verified u-boot available yet, I could not see any output on the screen :( Maybe I should build a u-boot myself?
Filed under: Chromebook

Today I not only submitted my bachelor thesis to the printing company, I also released a new version of hardlink, my file deduplication tool. hardlink 0.3 now features support for xattr support, contributed by Tom Keel at Intel. If this does not work correctly, please blame him. I also added support for a minimum-size option. Most of the other code has been tested since the upload of RC1 to experimental in September 2012. The next major version will split up the code into multiple files and clean it up a bit. It s getting a bit long now in a single file.
Filed under: Uncategorized

Today I not only submitted my bachelor thesis to the printing company, I also released a new version of hardlink, my file deduplication tool. hardlink 0.3 now features support for xattr support, contributed by Tom Keel at Intel. If this does not work correctly, please blame him. I also added support for a minimum-size option. Most of the other code has been tested since the upload of RC1 to experimental in September 2012. The next major version will split up the code into multiple files and clean it up a bit. It s getting a bit long now in a single file.
Filed under: Uncategorized

Today, we worked, with the help of ioerror on IRC, on reducing the attack surface in our fetcher methods. There are three things that we looked at:

1. Reducing privileges by setting a new user and group
2. chroot()
3. seccomp-bpf sandbox

Today, we implemented the first of them. Starting with 1.1~exp3, the APT directories /var/cache/apt/archives and /var/lib/apt/lists are owned by the _apt user (username suggested by pabs). The methods switch to that user shortly after the start. The only methods doing this right now are: copy, ftp, gpgv, gzip, http, https. If privileges cannot be dropped, the methods will fail to start. No fetching will be possible at all. Known issues:

• We drop all groups except the primary gid of the user
• copy breaks if that group has no read access to the files

We plan to also add chroot() and seccomp sandboxing later on; to reduce the attack surface on untrusted files and protocol parsing.
Filed under: Uncategorized

Since some time, those crappy Fritz!Box devices do not support WDS anymore, but rather a proprietary solution created by AVM. Now what happens if you have devices in another room that need/want wired access (like TVs, Playstations) or if you want to extend the range of your network? Buying another Fritz!Box is not very cost efficient What I did was to buy a cheap TP-Link TL-WR841N (can be bought for 18 euros) and installed OpenWRT on it. Here s how I configured it to act as a WiFi bridge. Basic overview: You configure OpenWRT into station mode (that is, as a WiFi client) and use relayd to relay between the WiFi network and your local network. You also need igmpproxy to proxy multicast packages between those networks, other UPnP stuff won t work. I did this on the recent Barrier Braker RC2. It should work on older versions as well, but I cannot promise it (I did not get igmpproxy to work in Attitude Adjustment, but that was probably my fault). Note: I don t know if it works with IPv6, I only use IPv4. You might want to re-start (or start) services after the steps, or reboot the router afterwards. Configuring WiFi connection to the FRITZ!Box Add to: /etc/config/network

config interface 'wwan'
	option proto 'dhcp'

(you can use any other name you want instead of wwan, and a static IP. This will be your uplink to the Fritz!Box) Replace wifi-iface in: /etc/config/wireless:

config wifi-iface
	option device 'radio0'
	option mode 'sta'
	option ssid 'FRITZ!Box 7270'
	option encryption 'psk2'
	option key 'PASSWORD'
	option network 'wwan'

(adjust values as needed for your network) Setting up the pseudo-bridge First, add wwan to the list of networks in the lan zone in the firewall. Then add a forward rule for the lan network (not sure if needed). Afterwards, configure a new stabridge network and disable the built-in DHCP server. Diff for /etc/config/firewall

@@ -10,2 +10,3 @@ config zone
 	list network 'lan'
+	list network 'wwan'
 	option input 'ACCEPT'
@@ -28,2 +29,7 @@ config forwarding
 
+# Not sure if actually needed
+config forwarding
+	option src 'lan'
+	option dest 'lan'
+
 config rule

Add to /etc/config/network

config interface 'stabridge'
	option proto 'relay'
	option network 'lan wwan'
	option ipaddr '192.168.178.26'

(Replace 192.168.178.26 with the IP address your OpenWRT router was given by the Fritz!Box on wlan0) Also make sure to ignore dhcp on the lan interface, as the DHCP server of the FRITZ!Box will be used: Diff for /etc/config/dhcp

@@ -24,2 +24,3 @@ config dhcp 'lan'
        option ra 'server'
+       option ignore '1'

Proxying multicast packages For proxying multicast packages, we need to install igmpproxy and configure it: Add to: /etc/config/firewall

# Configuration for igmpproxy
config rule
	option src      lan
	option proto    igmp
	option target   ACCEPT
config rule
	option src      lan
	option proto    udp
	option dest     lan
	option target   ACCEPT

(OpenWRT wiki gives a different 2nd rule now, but this is the one I currently use) Replace /etc/config/igmpproxy with:

config igmpproxy
	option quickleave 1
config phyint
	option network wwan
	option direction upstream
	list altnet 192.168.178.0/24
config phyint
	option network lan
	option direction downstream
	list altnet 192.168.178.0/24

(Assuming Fritz!Box uses the 192.168.178.0/24 network) Don t forget to enable the igmpproxy script:

# /etc/init.d/igmpproxy enable

Optional: Repeat the WiFi signal If you want to repeat your WiFi signal, all you need to do is add a second wifi-iface to your /etc/config/wireless.

config wifi-iface
	option device 'radio0'
	option mode 'ap'
	option network 'lan'
	option encryption 'psk2+tkip+ccmp'
	option key 'PASSWORD'
	option ssid 'YourForwardingSSID'

Known Issues If I was connected via WiFi to the OpenWRT AP and switch to the FRITZ!Box AP, I cannot connect to the OpenWRT router for some time. The igmpproxy tool writes to the log about changing routes. Future Work I ll try to get the FRITZ!Box replaced by something that runs OpenWRT as well, and then use OpenWRT s WDS support for repeating; because the FRITZ!Box 7270v2 is largely crap loading a page in its web frontend takes 5 (idle) 20 seconds (1 download), and it s WiFi speed is limited to about 20 Mbit/s in WiFi-n mode (2.4 GHz (or 5 GHz, does not matter), 40 MHz channel). It seems the 7270 has a really slow CPU.
Filed under: OpenWRT

Some days ago I decided to upgrade my laptop from stable to testing. I had tried Jessie since several months, in my husband s laptop, but that was a fresh install, and a not-so-old laptop, and we have not much software installed there. In my netbook (Compaq Mini 110c), with stable, I already had installed Pumpa, Dianara and how-can-i-help from testing, and since the freeze is coming, I thought that I could full-upgrade and use Jessie from now on, and report my issues and help to diagnose or fix them, if possible, before the freeze. I keep Debian stable at work for my desktop and servers (well, some of them are still in oldstable, thanks LTS team!!), and I have testing in a laptop that I use as clonezilla/drbl server (but I had issues, next week I ll put some time on them and I ll write here my findings, and report bugs, if any). So! let s go. Here I write my experience and the issues that I found (very few! and not sure if they are bugs or configuration problems or what, I ll keep an eye on them). The upgrade I pointed my /etc/apt/sources.list to jessie, then apt-get update, then apt-get dist-upgrade. (With the servers I am much more careful, read the release notes, upgrade guides and so, or directly I go for a fresh install, but with my laptop, I am too lazy). I went to bed (wow, risky LArjona!) and when I got up for going to work, the laptop was waiting for me to accept to block root from ssh access, or restart some services, and so. Ok! the upgrade resumed but I have to go to work and I wanted my laptop! Since all the packages were already downloaded, I closed the lid (double risky LArjona!) unplugged it, put everything in my bag, and catched the bus in time :) At the bus, I opened again the lid of my laptop (crossing fingers!) and perfect, the laptop had suspended and returned back to life, and the upgrade just resumed with no problem. Wow! I love you Debian! After 15 minutes, I had to suspend again, since the bus arrived and I had to take the metro. In the metro, the upgrade resumed, and finished. I shutdown my laptop and arrive to work. Testing testing :) In a break for lunch, I opened my brand new laptop (the hardware is the same, but the software totally renewed, so it s brand new for me). I have to say that use xfce, with some GNOME/GTK apps installed (gedit, cheese, evince, XChat ) and some others that use Qt or are part of the KDE project (Okular, Kile, QtLinguist, Pumpa, Dianara). I don t know/care too much about desktops and tweaking my desktop: I just put the terminal and gedit in black background, Debian wallpaper is enough dark for me so ok, put the font size a bit smaller to better use my low-vertical-resolution, and that s all, I only go to configure something else if there s something that really annoys me. My laptop booted correctly and a nice, more modern LightDM was greeting me. I logged in and everything worked ok, except some issues that follow. Network Manager and WPA2-enterprise wireless connections I had to reconfigure some wireless connections in Network Manager. At the University we use WPA2-enterprise, TTLS + PAP. I had stored my username and password in the connection, and network manager seemed to remember the username but not the password. No problem, I said, and I wrote it when it asked, but the Save or OK button was greyed out. I could not click it. Then I went to edit the connections, and more or less the same, it seems that I could edit, but not save the (new) configuration. Finally, I removed the wireless connection and created it again, and everything worked as a charm. This, I had to do it with the two wireless in my University (both of them are WPA2-enterprise TTLS + PAP). At home, I have WPA2 personal, and I had no issues, everything worked ok. This problem is not appearing in a fresh install, since there are no old configs to keep. Adblock Plus not working any more I opened Iceweasel and I began to see ads in the webpages that I visited. What? I checked and Adblock plus was installed and activated I reinstalled the package xul-ext-adblock-plus and it worked again. Strange display in programs based on Qt When I opened Pumpa I noticed that the edges of the windows where too rough, as if it was not using a desktop theme. I asked to a friend that uses Plasma and he suggested to install qt4-qtconfig, and then, select a theme for my Qt apps. It worked like a charm, but I find strange that I didn t need it before in stable. Maybe the default xfce configuration from stable is setting a theme, and the new one is not setting it, and so, the Qt apps are left barefoot .
With qtconfig I chose a GTK+ Style GUI for my Qt apps and then, they looked similar to what I had in stable (frankly, I cannot say if it was similar or exactly the same , but I didn t find them strange as before, so I m fine). Strange display in programs from GNOME Well, this is not a Jessie problem, it s just that some programs adopted the new GNOME appearance, and since I m on xfce, not on GNOME, they look a bit strange (no menus integration, and so). I am not sure that I can run GNOME (fallback, classic?) in my 1 GB RAM laptop, I have to investigate if I can tweak it to use less memory, or what. I m not very tied to xfce, and in fact it does not look so light (well, on top of it, I don t run light programs, I run Iceweasel, Icedove, Libreoffice, and some others). At work I use GNOME in my desktop, but with GNOME shell, not the fallback or classic modes, so I m thinking about giving a chance to MATE or second chance to LXDE. We ll see. Issues when opening the lid (waking up from suspend) This is the most strange thing I found in the migration, and the most dangerous one, I think. As I said before, I don t tweak too much my desktop, if it works with the default configuration. I m not sure that I know the differences between suspend, hibernate, hard disks disconnections and so. When I was in stable, and I closed the lid of my laptop, it just shutdown the screen, then I heard something like the system going to suspend or whatever, and after some seconds, the harddisk and fans stop, the wireless led turns off, and the power led begins to blink. Ok. When I open the lid, then it was waking up itself (the power led stayed on, the wireless led turns on, and when I tap the touchpad or type anything, the screen was coming, with the xscreensaver asking for my password). Just sometimes, when the screen was turning on, I could see my desktop for less than a second, before xscreensaver turns the background black and asks for the password. Now since I migrated to Jessie, I m experiencing a different behavior. When I close the lid, the laptop behaves the same. When I open the lid, the laptop behaves the same, but when I type or tap the touchpad and xscreensaver comes to ask the password, before than I can type it, the laptop just suspends again (or hibernates, I m not sure), and I have to press the power button in order to bring it back to life (then I see the xscreensaver again asking for the password, I type it, and my desktop is there, the same as I left it when I closed the lid). Strange, isn t it? I have tried to suspend my laptop directly from the menu, and it comes to the same state in which I have to press the power button in order to bring it back to life, but then, no xscreensaver password is required (which is double strange, IMHO). Things I miss in Jessie Well, until now, the only thing I miss in Jessie is the software center. I rarely use it (I love apt) but I think it makes a good job in easing the installation of programs in Debian for people coming from other operative systems (specially after smartphones and their copied software stores became popular). I hope the maintainer can upload a new version before the freeze, and so, it enters in the release. I ll try to contact him. Update 2014/07/20: Julian Andres Klode, maintainer of software-center, just replied (see his comment below) and pointed to GNOME Software (gnome-packagekit) as alternative. I just installed and it looks neat and nice. I m very happy! TODO I have a Debian stable laptop at work (this one with xfce + GNOME), I ll try to upgrade it and see if I see the same problems that I notice in mine. Then, I ll check the corresponding packages to see if there are open bugs about them, and if not, report them to their maintainers. I have to review the wiki pages related to the Jessie Desktop theme selection, I think they wanted the wallpaper to be inside before the freeze. Maybe I can help in publicity about that, handle the votings and so. I like Joy, but it s time to change a bit, new fresh air into the room!
Filed under: My experiences and opinion Tagged: Contributing to libre software, Debian, English, Free Software, Moving into free software

Today, I decided to set my X230 back to UEFI-only boot, after having changed that for a bios upgrade recently (to fix a resume bug). I then choose to save the settings and received several error messages telling me that the system ran out of resources (probably storage space for UEFI variables). I rebooted my machine, and saw no logo appearing. Just something like an underscore on a text console. The system appears to boot normally otherwise, and once the i915 module is loaded (and we re switching away from UEFI s Graphical Output Protocol [GOP]) the screen works correctly. So it seems the GOP broke. What should I do next?
Filed under: General

Today I made an important change to the python-apt code: It is now native Python 3 code (but also works under Python 2). The previous versions all run 2to3 during the build process to create a Python 3 version. This is no longer needed, as the code is now identical. As part of that change, python-apt now only supports Python 2.7, Python 3.3, and newer. I m using some features only present in 3.3 like Python2 unicode literal syntax in order to keep the code simple. Here s how I did it: I took the Python 2 code and ran 2to3 -f print -x future on it. This turned every print statement in a call to the print function. I then went ahead and added a from __future__ import print_function to the top of each module. This was the first commit. For the second commit, I ran 2to3 -p -x future to convert the remaining stuff to Python 3, and then undid some changes (like unicode literals) and fixed the rest of the changes to work under both Python 2 and 3. Sometimes I added a top-level code like:

if sys.version_info_major >= 3:
    unicode = str

So I could use unicode in the code for the Python 2 cases. I used various backported modules like io and stuff only available in Python 2.7, so dropped support for Python 2.6.
Filed under: Debian, Python

I released python-apt 0.9. This completely removes support for the old API from the code base (it was disabled for the entirety of 0.8 in Debian, and in Ubuntu since saucy). Highlights:

• Cleanup: Complete removal of old-api support code
• Bug fix: Various coverty bug fixes by Michael Vogt
• Bug fix: Correctly handles multi-arch dependencies in apt.debfile, so packagekit and gdebi can now install local multi-arch packages correctly
• Bug fix: A segmentation fault has been fixed. When releasing the value of the policy attribute of an apt_pkg.Cache object, its destructor deleted the pkgPolicy, but that was managed by a CacheFile from APT, causing it to be deleted twice.
• Bug fix: Tests do not depend on the contents of /tmp anymore
• Bug fix: All examples and old tests have been updated to the current python-apt API
• Feature: Paths can now be specified using bytes objects instead of str in Python 3.
• Ubuntu-specific: Meta-data for Ubuntu 14.04 although with a typo ( thar instead of tahr ), but that is fixed in git

Filed under: Debian

This week, a few hours after Lenovo announced the X240, I bought an X230. Normally, the X230 model I bought comes with a Core i5-3320M CPU, 4GB RAM, 500GB HDD. My model was a special set including a second 4GB RAM stick and a 128 GB mSATA Plextor SSD. It came without Windows; and the ThinkVantage button is black instead of blue and has no label. I put a fresh installation of unstable on it and tweaked it to save more power when on battery (enabled RC6++, and enabled autosuspend and other powertop suggestions with a script in /etc/pm/power.d); and configured hdparm.conf to put my hard disk into standby after 5 seconds (it s only used for big data anyway, so most of the time it is unused). It now consumes 5W in idle with minimum brightness, and 8-10W with brightness 13 of 15. Consumption when surfing is 10 15 watts. Booting from grub to gdm is fast, I did not measure it, but it probably took about 5 seconds. The IPS screen looks really good. Much much much better than the screen in my 2010 Edge 15 (I reviewed that one in 2010). It seems a bit more glossy than that one, but still matte. Keyboard is good as well. The touch pad is crap however. All hardware seems to work. Comparison to the X240 for others who think about buying one of them: The X240 is lighter and thinner (it s an Ultrabook) and has an optional FullHD 12.5 inch screen. It also offers a much larger touchpad and palm rest. But compared to the X230, the X240 lacks many things: No dedicated buttons for the trackpoint (you need to use the click-pad), it s limited at 8GB RAM, uses a slower low-voltage Haswell CPU, and it uses the new M.2 connector (probably supporting only the shortest cards) instead of mini-PCIe, so it s not really possible to add an additional SSD currently; as M.2 SSDs do not seem to be available yet. I also do not know whether the X240 offers ThinkLight or LEDs for hard drive activity and similar.
Filed under: General

The script apt-show-versions is developed by another Debian Developer called Christoph Martin in Perl. Recently, it turned out that apt-show-versions is too slow for some users; so I decided to rewrite his program using APT s C++ API. I expect this to be part of a future APT release, rendering the original apt-show-versions obsolete. The rewrite is sadly not 100% backwards compatible to the original version; as some option names had to be renamed due to our command-line parser not supporting option names like -nh, and some other options were dropped because they are hard to support (like status-file and lists-dir) with our command-line parsing. I also decided not to keep the the -p and -r options, but use the standard APT command-line conventions insteads. For now, it also cannot show you the distribution names you have specified in your sources.list file, but will always display codenames instead; if available. I hope to fix this in Jessie by extending APT s cache format a bit. On the performance side, this program now takes about 0.09s compared to the 1.40 seconds needed by apt-show-versions. The times are taken with all data in caches. The current version can be found in a git repository, a link to gitweb is: http://anonscm.debian.org/gitweb/?p=users/jak/apt-show-versions.git
Please also note that support for allversions is not 100% implemented yet, but it should work for most uses. Now, go testing and report back!
Filed under: Debian

Writing recursive descent parsers is easy, especially in Python (just like everything is easy in Python). But Python defines a low limit on the number of recursive calls that can be made, and recursive descent parsers are prone to exceed this limit. We should thus write our parser without real recursion. Fortunately, Python offers us a way out: Coroutines, introduced in Python 2.5 as per PEP 342. Using coroutines and a simple trampoline function, we can convert every mutually recursive set of functions into a set of coroutines that require constant stack space. Let s say our parser looks like this (tokens being an iterator over characters):

def parse(tokens):
    token = next(tokens)
    if token.isalnum():
        return token
    elif token == '(':
         result = parse(tokens)
         if next(tokens) != ')': raise ...
         return result
    else:
         raise ...

We now apply the following transformations:
return X => yield (X)
parse() => (yield parse()) That is, we yield the value we want to return, and we yield a generator whenever we want to call (using a yield expression). Our rewritten parser reads:

def parse(tokens):
    token = next(tokens)
    if token.isalnum():
        yield token
    elif token == '(':
         result = yield parse(tokens)
         if next(tokens) != ')': raise ...
         return result
    else:
         raise ...

We obviously cannot call that generator like the previous function. What we need to introduce is a trampoline. A trampoline is a function that manages that yielded generators, calls them, and passes their result upwards. It looks like this:

def trampoline(generator):
    """Execute the generator using trampolining. """
    queue = collections.deque()
    def schedule(coroutine, stack=(), value=None):
        def resume():
            if 0:
                global prev
                now = stack_len(stack)
                if now < prev:
                    print("Length", now)
                    prev = -1
                elif prev != -1:
                    prev = now
            result = coroutine.send(value)
            if isinstance(result, types.GeneratorType):     # Normal call
                schedule(result, (coroutine, stack))
            elif isinstance(result, Tail):                  # Tail call (if you want to)
                schedule(result.value, stack)
            elif stack:                                     # Return to parent
                schedule(stack[0], stack[1], result)
            else:                                           # Final Return
                return result
        queue.append(resume)
    schedule(generator)
    result = None
    while queue:
        func = queue.popleft()
        result = func()
    return result

This function is based on the code in PEP 342, the difference being that

• we do not correctly propagate exceptions through the stack, but directly unwind to the caller of the parser (we don t handle exceptions inside our parser generators anyway)
• the code actually compiles (code in PEP used value = coroutine.send(value) which does not work)
• the code returns a value (code in PEP was missing a return in schedule)
• we don t use a class, and allow only one function to be scheduled at once (yes, we could get rid of the queue)
• we allow tail calls [where Tail = namedtuple("Tail", ["result"])] to save some more memory.

For a more generic version of that, you might want to re-add exception passing, but the exceptions will then have long tracebacks, so I m not sure how well they will work if you have deep recursion. Now, the advantage of that is that our parser now requires constant stack space, because the actual real stack is stored in the heap using tuples which are used like singly-linked lists in scheme here. So, the only recursion limit is available memory. A disadvantage of that transformation is that the code will run slightly slower for small inputs that could be handled using a normally recursive parser.
Filed under: Python

You can use a PBO solver to clean up your system from unneeded automatically installed packages. First of all, you convert the system state to PB, and add an optimization function telling it to remove as many automatically installed packages as possible. Then you run this thing through a solver (such as clasp, which seems the fastest solver for PBO instances in the Debian archive) and convert its output to human-readable package names. Code is provided at http://anonscm.debian.org/gitweb/?p=users/jak/cleanup.git, under the MPL 2.0. You need to have python-apt and clasp installed to use it. There is potential minisat+ support, but it s currently a bit broken. To use, run python program_builder.py, and it will tell you which packages are no longer needed on your system. It ignores Suggests, if you want those in, you have to hack the code and replace Recommends by Recommends , Suggests . You can also turn of such dependencies by setting Program.hard_softdeps to False.
Filed under: APT2, Debian, Python

Debian packages commonly use or dependencies of the form a b to mean that a or b should be installed, while preferring option a over b. In general, for resolving an or dependency, we will try all options from the left to the right, preferring the left-most option. We also prefer real packages over virtual ones. If one of the alternatives is already installed we use that.

def solve_or(or):
  best_real = None
  best_virtual = None
  for dep in or:
     for target in dep:
        if target.name == dep.name and best_real is None:
           best_real = target
        if target.name != dep.name and best_virtual is None:
           best_virtual = target        
        if target.is_installed():
          return target
  return best_real if best_real is not None else best_virtual

Now, this way of solving dependencies is slightly problematic. Let us consider a package that depends on: a b, b. APT will likely choose to install a to satisfy the first dependency and b to satisfy the second. I currently have draft code around for a future version of APT that will cause it to later on revert unneeded changes, which means that APT will then only install b . This result closely matches the CUDF solvers and cupt s solver. On the topic of solving algorithms, we also have the problem that optimizing solvers like the ones used with apt-cudf do not respect the order of dependencies, rather choosing to minimise the number of packages installed. This causes such a solver to often do stuff like selecting an sqlite database as backend for some service rather then a larger SQL server, as that installs fewer packages. To make such solvers aware of the implicit preferences, we can introduce a new type of dependency category: Weak conflicts, also known as Recommends-Not. If a package P defines a Recommends-Not dependency against a package Q, then this means that Q should not be installed if P is installed. Now, if we have a dependency like: Depends: a b c we can encode this as: Recommends-Not: c, c, b Causing the solver to prefer a, then b, and then c. This should be representable as a pseudo-boolean optimization problem, as is common for the dependency problem, although I have not looked at that yet it should work by taking the standard representation of conflicts, adding a relaxation variable and then minimising [or maximising] the number of relaxation variables.
Filed under: APT2, Debian, General

In the past days, I looked at various memory allocators in a quest to improve performance in my multi-threaded test cases of a reference counting language runtime / object allocator (a fun project). It turns out the glibc s memory allocator is relatively slow, especially if you do loops that create one element and destroy one element at the same time (for example, map() on a list you no longer use after you passed it to map). To fix this problem, I considered various options. The first option was to add a thread-local cache around malloc(). So whenever we want to free() an object, we place it on a thread-local list instead, and if a malloc() request for an object of that size comes in, we reuse the old object. This fixes the problem with the lists, but experiments shown another problem with the glibc allocator: Allocating many objects without releasing others (let s say appending an element to a functional list). I started testing with tcmalloc instead, and noticed that it was several times faster (reducing run time from 6.75 seconds to 1.33 seconds (5 times faster)). As I do not want to depend on a C++ code base, I decided to write a simple allocator that allocates blocks of memory via mmap(), splits those into objects, and puts the objects on a local free list. That allocator performed faster than tcmalloc(), but was also just a simple test case, and not really useable, due to potential fragmentation problems (and because the code was statically linked in, causing thread-local storage to be considerably faster, as it does not need to call a function on every TLS access, but can rather go through a segment register). I then discovered jemalloc, and tried testing with this. It turned out that jemalloc was even faster than tcmalloc in all test cases, and also required about the same amount of memory as tcmalloc (and slightly more than the custom test code, as that combined reference counting with memory allocator metadata and thus had less meta data overhead). Using jemalloc, the list building test performs in 0.9X seconds now (instead of tcmalloc s 1.33 or glibc s 6.75 seconds), requires 0 major page faults (tcmalloc has 2), and uses 5361472 kb memory (tcmalloc uses 5290240, glibc requires 7866608). Given that jemalloc is written in C, I can only recommend it to everyone in need of a scalable memory allocator. Depending on your workload, it might require less memory than tcmalloc (at least that s the case at Facebook) and is most likely faster than tcmalloc. It also provides tcmalloc-compatible profiling facilities (as Facebook needed them). Furthermore, jemalloc is also the memory allocator used by FreeBSD, and is used by Mozilla projects, and on several Facebook projects, and should thus be relatively stable and useable. All tests were run with 4 threads, on a dual-core laptop with hyper-threading, using (e)glibc 2.13, tcmalloc 2.0, and jemalloc 3.0. The tests may not be representative of real world performance, and do not account for fragmentation. Should I try replacing Python s custom caching of malloc() calls with simply calling jemalloc, and run a few Python benchmarks? Anyone interested in that?
Filed under: General

One thing I thought about today is reference counting in combination with tail calls. Imagine a function like this:

function f(x)   return g(x+1);  

Now consider that x is a reference counted object and that x + 1 creates a new object. The call to g(x + 1) shall be in tail call position. In most reference counted languages, the reference to an argument is owned by the caller. That is, f() owns the reference to x + 1. In that case, the call to g() would no longer be in a tail call position, as we still have to decrease the reference count after g() exits. An alternative would be that the callee owns the reference. This however, will most likely create far more reference count changes than a caller-owns language (increase reference count in caller, decrease reference count in callee). For example, the following function requires an increment before the call to g().

function f1(x)   return g(x);  

Does anyone have any ideas on how to solve the problem of tail calls while avoiding the callee-owns scenario? Something that does not require a (non-reference-counting) garbage collector would be preferably.
Filed under: General

In the language introduced yesterday, mutable parameters play the important role of representing the side effects of actions in the type system and thus ensure referential transparency. One of the questions currently unaddressed is how to handle currying in the presence of mutable parameters. In order to visualise this problem, consider a function

    printLn(mutable IO, String line)

If we bind the the first parameter, what should be the type of the function, and especially important how do we get back the mutable parameter? Consider the partially applied form printLn1:

    printLn1(String line)

The mutability parameter would be lost and we could not do any further I/O (and the curried form would appear as a pure function, so a good compiler would not even emit a call to it) An answer might be to put the thing into the result when currying:

    printLn2(String line) -> mutable IO

But how can we explain this? In the end result, do we maybe have to use a signature like:

    printLn(String, mutable in IO io1, mutable out IO io2)

We could then introduce syntax to call that as

    printLn(string, mutable io)

Where as the mutable io argument basically expands to io and io1 for the first call, and for later calls to io1, io2 , and so on. It can also be easily curried by allowing currying to take place on variables not declared as output parameters. We can then curry the function as:

    printLn3(mutable in IO io1, mutable out IO io2)
    printLn4(mutable out IO io2)

If so, we can rename mutable back to unique and make that easier by introducing the unary operator & for two locations, just like Mercury uses ! for it. We could then write calls looking like this:

    printLn("Hello", &io);
    printLn("Hello", io, io1);

How out parameters are explained is a different topic; we could probably say that an out parameter defines a new variable. Another option is to forbid currying of mutable parameters entirely. This would have the advantage of maintaining the somewhat simple one parameter style. The programming language Clean does not provide any special syntactic sugar for having mutable variables. In Clean, the function gets a unique object and returns a unique object (noted by *). For example, the main entry point in a Clean program (with state) looks like this:

    Start:: *World -> *World

In short, the function Start gets a abstract world passed that is unique and at the end returns a new unique world. In Clean syntax, our example function would most likely have the signature:

    printLn :: String *IO -> *IO

You know have to either maintain one additional variable for the new unique object, which gets a bit complicated with time. On the other hand, you can do function composition on this (if you have a function composition operator that preserves uniqueness when available, as should be possible in Clean):

    printTwoLines :: *IO -> *IO
    printTwoLines = (printLn "World") o (printLn "Hello")

Function composition on mutable things however, does not seem like it is needed often enough in a functional programming language with a C syntax. People might also ask why monads are not used instead. Simon L Peyton Jones and Philip Wadler described monadic I/O in their paper Imperative Functional Programming (http://research.microsoft.com/en-us/um/people/simonpj/papers/imperative.ps.Z) in 1993, and it is used in Haskell (the paper was about the implementation in Haskell anyway), one of the world s most popular and successful functional programming languages. While monadic I/O works for the Haskell crowd, and surely some other people, the use of Monads also limits the expressiveness of code, at least as far as I can tell. At least as soon as you want to combine multiple monads, you will have to start lifting stuff from one monad to another (liftIO and friends), or perform all operations in the IO monad, which prevents obvious optimizations (such as parallelizing the creation of two arrays) in short dependencies between actions are more strict than they have to be. For a functional language targeting imperative programmers, the lifting part seems a bit too complicated. One of the big advantages of monads is that they are much easier to implement, as they do not require extensions to the type system and the Hindley-Milner type inference algorithm used by the cool functional programming languages. If you want uniqueness typing however, you need to modify the algorithm or infer the basic types first and then infer uniqueness in a second pass (as Clean seems to do it).
Filed under: General

Just for you, and this time in the Pythonesque rendering.

module main:
    import std (range)
    import std.io (printf, IO)
    # print the Fahrenheit-Celcius table for fahr = 0, 20, ..., 300
    function main(mutable IO io):
        Int lower = 0    # lower bound
        Int upper = 300  # upper bound
        Int step = 20    # step
        for Int fahr in range(lower, upper, step):
            Double celcius = 5 * (fahr - 32) / 9
            std.io.printf(io, "%3d\t%6.1f\n", fahr, celcius)

It does not really look like it, but this language is purely functional. It represents side effects using unique types. If you declare a mutable parameter, you basically declare a unique input parameter and a unique output parameter. I m also giving you a list implementation

module std.container.list:
    ## The standard singly-linked list type
    type List[E]:
        Nil                     ## empty list
        Node:
            E value             ## current value
            List[E] next        ## remaining list
 

And yes, both languages should be able to be represented using the same abstract syntax tree. The only change is the replacement of the opening curly brace by a colon, the removal of the closing curly bracket and semicolons, the replacement of C-style comments with Python-style comments and the requirement of indentation; oh and the for statement gets a bit lighter as well.
Filed under: General

Just for you:

module main  
    import std (range);
    import std.io (printf, IO);
    /* print the Fahrenheit-Celcius table
        for fahr = 0, 20, ..., 300 */
    function main(mutable IO io)  
        Int lower = 0;   // lower bound
        Int upper = 300; // upper bound
        Int step = 20;   // step
        for (Int fahr in range(lower, upper, step))  
            Double celcius = 5 * (fahr - 32) / 9;
            std.io.printf(io, "%3d\t%6.1f\n", fahr, celcius);
         
     
 

It does not really look like it, but this language is purely functional. It represents side effects using unique types. If you declare a mutable parameter, you basically declare a unique input parameter and a unique output parameter. I m also giving you a list implementation

module std.container.list  
    /** The standard singly-linked list type */
    type List[E]  
        Nil;                    /** empty list */
        Node  
            E value;            /** current value */
            List[E] next;       /** remaining list */
         
     
 

Thus are only excerpts from a document with tens of pages and the reference implementation of the standard library. The incomplete working draft for the language is attached: JAK Programming Language Early Working Draft (28 pages). Update: Fixed the link.
Filed under: General

I have just released version 0.2 RC1 of my hardlink program. Compared to the 0.1.X series, the program has been rewritten in C, as Python was to memory-hungry for people with millions of files. The new program uses almost the same algorithm and has almost completely the same bugs as the old version. The code should be portable to all UNIX-like platforms supporting nftw(). I have tested the code on Debian, FreeBSD 9, and Minix 3.2. For storing path names, it uses a flexible array member on C99 compilers, a zero-length-array on GNU compilers, and a array of length 1 on all other compilers (which should work everywhere as far as I heard). The new version may have slightly different behaviour compared to 0.1.2 when regular expressions are specified on the command-line, as a result of the switch from Python s regular expression engine to PCRE (if compiled with PCRE support, you can also use POSIX extended regular expressions if you like). The code is significantly faster than the old code (in situations where it s not I/O bound), and uses much less memory than the old one. Per file, we now store a <tt>struct stat</tt>, a pointer, an int, a char, and the filename; as well as three pointers for a binary search tree (which uses tsearch()). It should also be compatible to Red Hat s original hardlink tool now command-line-wise, there is at least a -c option now. The history and the name conflict are interesting, but probably nothing for this post. We re even less resistant against changing trees than Fedora s tool (and derived) currently, but should otherwise be better (and far more complicated and feature-packed). And we don t require mmap(), but use fread() instead. There was no real performance difference in testing. And we are not GPL-licensed, but use the MIT/Expat license. The package is currently entering Debian experimental for testing purposes. If you have used hardlink previously, or are just curious, give it try. And the makefile is now compatible with the various BSD makes out there, if that s interesting for you. Link to website: http://jak-linux.org/projects/hardlink/
Filed under: General